import java.util.LinkedList;
import java.util.Queue;

/**
 * @author LKQ
 * @date 2022/1/1 10:04
 * @description 广度优先遍历，一般需要队列辅助统计初始结点所有的邻接结点，然后循环往复
 */
public class Solution {
    int[] dx = {1, 0, 0, -1};
    int[] dy = {0, 1, -1, 0};

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] image = {{1,1,1}, {1,1,0}, {1,0,1}};
        solution.floodFill(image, 1, 1, 2);
    }

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        // 记录当前颜色
        int currColor = image[sr][sc];
        if (currColor == newColor) {
            // 如果当前颜色与新颜色相同，不用覆盖
            return image;
        }
        int n = image.length, m = image[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{sr, sc});
        image[sr][sc] = newColor;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            // 结点的x, y坐标
            int x = cell[0], y = cell[1];
            for (int i = 0; i < 4; i++) {
                // 上下左右四个方向判断是否相同
                int mx = x + dx[i], my = y + dy[i];
                if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) {
                    queue.offer(new int[]{mx, my});
                    image[mx][my] = newColor;
                }
            }
        }
        return image;
    }
}
